package com.doubleview.demo

import groovy.transform.TailRecursive

/**
 * @author huchengchao@kuaishou.com
 * Created on 2021-11-20
 */
//==================尾递归=============================

/**
 * 为什么这个方法不是尾递归？
 * 如果它的返回值是 n * factorial(n-1)，那么本次调用就需要等待下一次调用的 factorial(n-1) 来计算返回值。
 * 因此，假定 n == 3 , 那么线程就需要 3 层栈空间来解决它。
 * 假定 n 取了更大的值 , 那么 JVM 就会呻吟了。
 * @param n
 * @return
 */
int factorial(int n) {
    return n <= 1 ? 1 : n * factorial(n - 1)
}

/**
 * 为什么这个方法是尾递归？
 * 无论是哪个分支，该递归函数总是返回一个数值或者发起一个新的调用，且当前调用没有需要等待的后续运算了。
 * 而递归过程的中间结果会不断地被装入 acc 参数中并传递。
 * 所以，在当前调用结束之后，它可以安全地 "传宗接代且无后顾之忧"。
 * 无论 n 取何值，这个尾递归始终只占用 1 层栈空间。
 * 唯一不太方便的是，用户调用这个函数需要主动为 acc 传递一个初始值，而我们一般都靠包装函数来解决这个瑕疵。
 * @param n
 * @return
 */
@TailRecursive
int factorial_t(int n, int acc) {
    return n <= 1 ? acc : factorial_t(n - 1, acc * n)
}

// good
println factorial_t(10000, 1)

/**
 * 递归闭包
 */
// 对于递归闭包，我们必须先定义出一个变量作为它的名字，才能在闭包内部调用自身。
factorial_closure = {
    i, BigInteger n = 1 -> i <= 1 ? n : factorial_closure.trampoline(i - 1, n * i)
}.trampoline()
factorial_closure(1000)